import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left==null&&right==null){
            return null;
        }
        if(left==null&&right!=null){
            return right;
        }
        if(left!=null&&right==null){
            return left;
        }
        return root;
    }







    int index,k;
    public int kthLargest(TreeNode root, int k) {
        this.k=k;
        dfs(root);
        return index;
    }
    public void dfs(TreeNode t){
        if(t==null){
            return;
        }
        dfs(t.right);
        if(k==0){
            return ;
        }
        if(--k==0){
            index=t.val;
        }
        dfs(t.left);
    }






    List<Double> list=new ArrayList<>();
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null){
            queue.add(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                double sum=0;
                for(int i=0;i<size;i++){
                    TreeNode node=queue.poll();
                    sum+=(double) node.val;
                    if(node.left!=null){
                        queue.offer(node.left);
                    }
                    if(node.right!=null){
                        queue.offer(node.right);
                    }
                }
                list.add(sum/size);
            }
        }
        return list;
    }







    public String tree2str(TreeNode root) {
        if(root==null){
            return "";
        }
        if(root.left==null&&root.right==null){
            return root.val+"";
        }
        if(root.right==null){
            return root.val+"("+tree2str(root.left)+")";
        }
        return root.val+"("+tree2str(root.left)+")"+"("+tree2str(root.right)+")";
    }





    int sum2=0;
    public int findTilt(TreeNode root) {
        sum2=0;
        dfs1(root);
        return sum2;
    }
    public int dfs1(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=dfs(root.left);
        int right=dfs(root.right);
        sum2+=Math.abs(left-right);
        return left+right+root.val;
    }





    int sums=0;
    public int diameterOfBinaryTree1(TreeNode root) {
        dfs(root);
        return sums;
    }
    public int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=dfs(root.left);
        int right=dfs(root.right);
        sums=Math.max(sums,left+right);
        return Math.max(left,right)+1;
    }








    static int sum1=0;
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null){
            return 0;
        }
        if(root.left!=null&&(root.left.left==null&&root.left.right==null)){
            sum1+=root.left.val;
        }
        sumOfLeftLeaves(root.left);
        sumOfLeftLeaves(root.right);
        return sum1;
    }








    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if((root.val-p.val)*(root.val-q.val)<=0){
            return root;
        }
        return lowestCommonAncestor(p.val<root.val?root.left:root.right,p,q);
    }





    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }




    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null){
            return false;
        }
        if(root.left==null&&root.right==null){
            return targetSum==root.val;
        }
        return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);
    }




    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int TreeLeft=minDepth(root.left);
        int TreeRight=minDepth(root.right);
        return root.left==null||root.right==null?TreeLeft+TreeRight+1:Math.min(TreeLeft,TreeRight)+1;
    }
}
